package algocasts;

public class P104_PartitionList {
    class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode smaller = new ListNode(0), greater = new ListNode(0);
        ListNode ps = smaller, pg = greater;
        for (ListNode p = head; p != null; p = p.next) {
            if (p.val < x) {
                ps.next = p;
                ps = ps.next;
            } else {
                pg.next = p;
                pg = pg.next;
            }
        }
        ps.next = greater.next;
        pg.next = null;
        return smaller.next;
    }
}
